package com.ljx.Dynamic;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author 李加喜
 * @Package com.ljx.Dynamic
 * @date 2021-11-03 22:33
 */
// 回溯求路径
public class Three {
    public static void main(String[] args) {

    }

    List<List<Integer>> res = new LinkedList<>();

    public List<List<Integer>> permute(int[] nums) {
        // 存储当前记录的路径
        LinkedList<Integer> tarckList = new LinkedList<>();
        dp(nums, tarckList);
        return res;
    }

    // 路径：记录在 track 中
// 选择列表：nums 中不存在于 track 的那些元素
// 结束条件：nums 中的元素全都在 track 中出现
    private void dp(int[] nums, LinkedList<Integer> tarckList) {
        if (nums.length == tarckList.size()) {
            res.add(new LinkedList<>(tarckList));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (tarckList.contains(nums[i])) {
                continue;
            }
            tarckList.add(nums[i]);
            dp(nums, tarckList);
            tarckList.removeLast();
        }
    }
}
